package leecode

import "math"

func minWindow(s string, t string) (result string) {
	//滑动窗口的左右指针
	resLen := math.MaxInt
	left, right := 0, 0
	// hashMap key为t的字母 value为t中每个字母对应的个数
	hashMap := make(map[byte]int)
	for index, _ := range t {
		hashMap[t[index]]--
	}
	diff := len(hashMap)
	//移动窗口
	for right < len(s) {
		if _, ok := hashMap[s[right]]; ok {
			hashMap[s[right]]++
			//当某一个字符出现的次数为0时,表示该字母已经实现了覆盖
			if hashMap[s[right]] == 0 {
				diff--
			}
		}
		//当哈希表中所有字母出现次数都为0时 , 则说明窗口中的已经包含了字符串t
		//包含时 窗口左边右移 , 排除元素
		for diff == 0 {
			if _, ok := hashMap[s[left]]; ok {
				//窗口右移,如果hash表中包含左移的元素,出现次数-1
				hashMap[s[left]]--
				//如果窗口右移使某一个元素消失在窗口中 , diff++ , 表示依旧有元素未被覆盖
				if hashMap[s[left]] < 0 {
					diff++
					//刚好消失时,此时的解为此次最优解
					if right-left+1 < resLen {
						result = s[left : right+1]
						resLen = len(result)
					}
				}
			}
			//窗口左边界右移
			left++
		}
		right++
	}
	return
}
